package leetcode.year2021.month11;

// 543. 二叉树的直径
public class _11_4DiameterOfBinaryTree543 {
  // 解题思路， 实现一个当前树最大深度的方法， 然后递归，维护一个最大结果
  int maxLength = 0;

  public int diameterOfBinaryTree(TreeNode root) {
    if (root == null){
      return 0;
    }
    getMaxLength(root);
    return maxLength;
  }

  public int getMaxLength(TreeNode root){
    // 求得当前树的最大高度，并且为返回值
    int leftHeight = 0;
    int rightHeight = 0;
    if (root.left == null && root.right == null){
      return 0;
    }

    if (root.left != null){
      leftHeight = getMaxLength(root.left) + 1;
    }

    if (root.right != null){
      rightHeight = getMaxLength(root.right) + 1;
    }

    // 计算通过当前root节点的最长直径，并与maxLength比较，最长直径，由左右子树返回值返回
    maxLength = Math.max(leftHeight+rightHeight,maxLength);

    return Math.max(leftHeight,rightHeight);
  }

  /**
   * 543. 二叉树的直径
   * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
   * <p>
   * <p>
   * <p>
   * 示例 :
   * 给定二叉树
   * <p>
   * 1
   * / \
   * 2   3
   * / \
   * 4   5
   * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
   * <p>
   * <p>
   * <p>
   * 注意：两结点之间的路径长度是以它们之间边的数目表示。
   */


  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
      this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}
